import java.util.ArrayList;
import java.util.Stack;

/**
 * 输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。
 * 如输入{1,2,3}
 * 返回一个数组为[3,2,1].
 *
 * Date: 2022-09-29
 * Time: 20:43
 */

// 实现一个简单的单链表
class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class Algorithm {

    public ListNode head = null;

    // 尾插
    public void addLast(int val) {
        ListNode newNode = new ListNode(val);

        if(head == null) {
            head = newNode;
        } else {
            ListNode cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = newNode;
        }
    }

    // 打印
    public void print(ListNode listNode) {
        System.out.print("[");
        ListNode list = listNode;
        while(list != null) {
            if(list.next != null)
                System.out.print(list.val + ", ");
            else
                System.out.print(list.val);
            list = list.next;
        }
        System.out.println("]");
    }


    // // 方案二: 递归
    private static void printListFromTailToHeadChild(ListNode listNode, ArrayList<Integer> list)  {
        if(listNode == null) { return; }

        printListFromTailToHeadChild(listNode.next,list);
        list.add(listNode.val);
    }
    public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> arrayList = new ArrayList<>();

        if(listNode == null) { return arrayList; }

        /*
        // 方案一: 用栈 顺序入栈 再顺序出栈
        Stack<Integer> stack = new Stack<>();
        ListNode cur = listNode;
        while(cur != null) {
            stack.push(cur.val);
            cur = cur.next;
        }
        while(!stack.empty()) {
            arrayList.add(stack.pop());
        }
        return arrayList;
        */

        // 方案二: 递归.[重点]
        printListFromTailToHeadChild(listNode,arrayList);
        return arrayList;
    }

}
